1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| #include<stdio.h>
#include<cstring>
#include<algorithm>
#include<string.h>
#include<iostream>
#include<cmath>
#include<set>
#include<queue>
#define mem(x,y) memset(x,y,sizeof(x))
#define maxn 50008
#define maxe 400008
#define inf 0x3f3f3f3f
#define mp(x,y) make_pair(x,y)
using namespace std;
bool cango(int x,int y)
{
return x>=0&&x<8&&y>=0&&y<8;
}
int X[]={-1,-2,1,2,1,2,-1,-2},Y[]={-2,-1,-2,-1,2,1,2,1};
int a[80][80];
int main()
{
for(int i=0;i<64;i++)
for(int j=0;j<64;j++)
a[i][j]=inf;
for(int i=0;i<64;i++)
a[i][i]=0;
for(int i=0;i<64;i++)
{
for(int k=0;k<8;k++)
if(cango(i/8+X[k],i%8+Y[k]))
a[i][(i/8+X[k])*8+i%8+Y[k]]=1;
}
for(int k=0;k<64;k++)
for(int i=0;i<64;i++)
for(int j=0;j<64;j++)
{
a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
}
char s1[5],s2[5];
while(~scanf("%s%s",s1,s2))
{
printf("To get from %s to %s takes ",s1,s2);
int x1=s1[0]-'a',x2=s2[0]-'a';
int y1=s1[1]-'1',y2=s2[1]-'1';
int x=x1*8+y1;
int y=x2*8+y2;
printf("%d knight moves.\n",a[x][y]);
}
}
|